Search for: All records

Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about Linearity testing in order to resolve two recent versions of this task. First, we focus on the online-manipulation-resilient model introduced by Kalemaj, Raskhodnikova and Varma (Theory of Computing 2023). In this model, up to t data entries are adversarially manipulated after each query is answered. Ben-Eliezer, Kelman, Meir, and Raskhodnikova (ITCS 2024) showed an asymptotically optimal Linearity tester that is resilient to t manipulations per query, but fails if t is too large. We simplify their analysis for the regime of small t, and for larger values of t we instead use sample-based testers, as defined by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A key observation is that sample-based testing is resilient to online manipulations but still achieves optimal query complexity for Linearity when t is large. We complement our result by showing that when t is very large any reasonable property, and in particular Linearity, cannot be tested at all. Second, we consider Linearity over the reals with proximity parameter ε. Fleming and Yoshida (ITCS 2020) gave a tester using O(1/ε · log(1/ε)) queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses O(1/ε) queries. This modification works for the low-degree testers presented in Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 2023) as well, resulting in optimal testers for degree-d polynomials, for any constant d. 

Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about Linearity testing in order to resolve two recent versions of this task. First, we focus on the online-manipulation-resilient model introduced by Kalemaj, Raskhodnikova and Varma (Theory of Computing 2023). In this model, up to t data entries are adversarially manipulated after each query is answered. Ben-Eliezer, Kelman, Meir, and Raskhodnikova (ITCS 2024) showed an asymptotically optimal Linearity tester that is resilient to t manipulations per query, but fails if t is too large. We simplify their analysis for the regime of small t, and for larger values of t we instead use sample-based testers, as defined by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A key observation is that sample-based testing is resilient to online manipulations but still achieves optimal query complexity for Linearity when t is large. We complement our result by showing that when t is very large any reasonable property, and in particular Linearity, cannot be tested at all. Second, we consider Linearity over the reals with proximity parameter ε. Fleming and Yoshida (ITCS 2020) gave a tester using O (1/ε · log (1/ε)) queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses O (1/ε) queries. This modification works for the low-degree testers presented in Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 2023) as well, resulting in optimal testers for degree-d polynomials, for any constant d. 

We study the problem of robust multivariate polynomial regression: let p: ℝⁿ → ℝ be an unknown n-variate polynomial of degree at most d in each variable. We are given as input a set of random samples (𝐱_i,y_i) ∈ [-1,1]ⁿ × ℝ that are noisy versions of (𝐱_i,p(𝐱_i)). More precisely, each 𝐱_i is sampled independently from some distribution χ on [-1,1]ⁿ, and for each i independently, y_i is arbitrary (i.e., an outlier) with probability at most ρ < 1/2, and otherwise satisfies |y_i-p(𝐱_i)| ≤ σ. The goal is to output a polynomial p̂, of degree at most d in each variable, within an 𝓁_∞-distance of at most O(σ) from p. Kane, Karmalkar, and Price [FOCS'17] solved this problem for n = 1. We generalize their results to the n-variate setting, showing an algorithm that achieves a sample complexity of O_n(dⁿlog d), where the hidden constant depends on n, if χ is the n-dimensional Chebyshev distribution. The sample complexity is O_n(d^{2n}log d), if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most O(σ), and the run-time depends on log(1/σ). In the setting where each 𝐱_i and y_i are known up to N bits of precision, the run-time’s dependence on N is linear. We also show that our sample complexities are optimal in terms of dⁿ. Furthermore, we show that it is possible to have the run-time be independent of 1/σ, at the cost of a higher sample complexity. 

We study the problem of robust multivariate polynomial regression: let p\colon\mathbb{R}^n\to\mathbb{R} be an unknown n-variate polynomial of degree at most d in each variable. We are given as input a set of random samples (\mathbf{x}_i,y_i) \in [-1,1]^n \times \mathbb{R} that are noisy versions of (\mathbf{x}_i,p(\mathbf{x}_i)). More precisely, each \mathbf{x}_i is sampled independently from some distribution \chi on [-1,1]^n, and for each i independently, y_i is arbitrary (i.e., an outlier) with probability at most \rho < 1/2, and otherwise satisfies |y_i-p(\mathbf{x}_i)|\leq\sigma. The goal is to output a polynomial \hat{p}, of degree at most d in each variable, within an \ell_\infty-distance of at most O(\sigma) from p. Kane, Karmalkar, and Price [FOCS'17] solved this problem for n=1. We generalize their results to the n-variate setting, showing an algorithm that achieves a sample complexity of O_n(d^n\log d), where the hidden constant depends on n, if \chi is the n-dimensional Chebyshev distribution. The sample complexity is O_n(d^{2n}\log d), if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most O(\sigma), and the run-time depends on \log(1/\sigma). In the setting where each \mathbf{x}_i and y_i are known up to N bits of precision, the run-time's dependence on N is linear. We also show that our sample complexities are optimal in terms of d^n. Furthermore, we show that it is possible to have the run-time be independent of 1/\sigma, at the cost of a higher sample complexity.